/*
 * @lc app=leetcode.cn id=1763 lang=cpp
 *
 * [1763] 最长的美好子字符串
 */

// @lc code=start
class Solution
{
public:
    void dfs(string s, int start, int end, int &maxPos, int &maxLen)
    {
        if (start >= end)
        {
            return;
        }
        int lower_bit = 0, upper_bit = 0;
        for (int i = start; i <= end; i++)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
            {
                lower_bit |= 1 << (s[i] - 'a');
            }
            else
            {
                upper_bit |= 1 << (s[i] - 'A');
            }
        }
        // 找到完美子串，更新起始点和长度
        if (lower_bit == upper_bit)
        {
            if (end - start + 1 > maxLen)
            {
                maxLen = end - start + 1;
                maxPos = start;
            }
            return;
        }
        // 上面未找到，以非法字符为切割点，递归查找其他区间
        // 所有合法的字符
        int valid = lower_bit & upper_bit;
        int pos = start;
        while (pos <= end)
        {
            start = pos;
            while (pos <= end && (valid & (1 << (tolower(s[pos]) - 'a'))))
            {
                pos++;
            }
            dfs(s, start, pos - 1, maxPos, maxLen);
            pos++;
        }
    }

    string longestNiceSubstring(string s)
    {
        int n = s.size();
        int max_pos = 0, max_len = 0;
        dfs(s, 0, n - 1, max_pos, max_len);
        return s.substr(max_pos, max_len);
    }
};
// @lc code=end
